1736E - Swap and Take - CodeForces Solution

n,a=int(input()),list(map(int,input().split()))
INF=10**9+7
f=[[-INF]*(n+1) for j in range(n+1)]
s=[[0]*(n+1) for j in range(n+1)]
ans=-INF
for i in range(1,n+1):
	for j in range(n,0,-1):
		for k in range(i,-1,-1):	
			if k:
				f[j][k]=f[j][k-1]+a[j-1]
			if j>=i and i+k>=j:
				f[j][k]=max(f[j][k],s[j-1][i+k-j]+a[j-1])
			ans=max(ans,f[j][k])
	for j in range(1,n+1):
		for k in range(i+1):
			s[j][k]=max(s[j-1][k],f[j][k])
print(ans)